#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp(500, 0);
        int n = days.size() - 1;
        for (int i = 365; i >= 1; i--)
        {
            if (n >= 0 && days[n] == i)
            {
                dp[i] = min(dp[i + 30] + costs[2], min(dp[i + 1] + costs[0], dp[i + 7] + costs[1]));
                n--;
            }
            else dp[i] = dp[i + 1];
        }
        return dp[1];
    }
};